package com.cet.qz.unit01.chapter1_3;

/**
 * @program: algorithm
 * @description: 栈的可生成性
 * @author: 陈恩涛
 * @create: 2021-04-26 10:29
 **/
public class Qz1_3_45 {

    /**
     * 判断序列是否会产生栈下溢
     * @param seq
     * @return
     */
    public static boolean isUnderflow(String[] seq) {
        int count = 0;
        for (String s : seq) {
            if ("-".equals(s)) {
                count--;
                if (count < 0) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 生成运行结果为result的混合序列
     * a<b<c  1.c 2.a 3.b 禁止出现这样的排列
     * @param result
     * @return
     */
    public static String[] generateSequence(String[] result) {
        String[] mixSeq = new String[result.length * 2];
        Stack<String> stack = new Stack<>();
        // 升序自然数生成数 0,1,2,3……
        int n = 0;
        //生成序列的数组下标
        int i = 0;
        for (String s : result) {
            while (n <= Integer.parseInt(s)) {
                stack.push(String.valueOf(n));
                mixSeq[i++] = String.valueOf(n);
                n++;
            }
            if (stack.peek().equals(s)) {
                stack.pop();
                mixSeq[i++] = "-";
            } else {
                throw new RuntimeException("栈输出结果有误，无法生成该结果的序列！");
            }
        }
        return mixSeq;
    }

    /**
     * 思路；序列中第n个元素小于第n+1个元素，若前n-1个元素存在比第n+1个元素大的元素则该序列不合法
     * @param seq
     * @return
     */
    public static boolean isAbleToGen(String[] seq) {
        int max = -1;
        int current;
        int previous = -1;
        for (String s : seq) {
            current = Integer.parseInt(s);
            if (current > previous && current < max) {
                return false;
            } else if (current > max) {
                max = current;
            }
            previous = current;
        }
        return true;
    }


    public static void main(String[] args) {
        String[] seq1 = {"a","b","c","-","-","-","d","-","-"};
        System.out.println("出入栈是否产生了栈向下溢出："+isUnderflow(seq1));

        String[] successSeq = {"5","4","3","2","1","0"};
        for (String s : generateSequence(successSeq)) {
            System.out.print(s+" ");
        }

        System.out.print("\n");

        String[] failSeq = {"2","3","1","0"};

        System.out.println("该序列能否由栈输出："+isAbleToGen(failSeq));
    }
}
